Moore's Law states that the growth rate of transistors per chip is exponential. Assuming that a fraction of these transistors being used to create state bits (e.g., latches, flip-flops or other memory elements) has remained constant, it follows that the growth rate of state bits in digital systems is also exponential. The complexity of functionally testing a system grows exponentially with the number of state bits (e.g., doubling the number of state bits implies that there are four times as many possible states to be tested). Thus, the complexity of functionally testing or verifying a digital system has a growth rate that is doubly exponential. Growth in verification complexity has been empirically observed as the number of pre-silicon logic bugs in semiconductor chips increases exponentially at a rate of 3-4 times per product generation.
A functional verification process can be divided into three steps. First, a test plan is constructed defining the desired scenarios to be tested. Next, test cases are created and run to test each scenario. Each test case should sensitize one or more of the scenarios of interest, predict an expected outcome, and check the actual outcome from running the tests against this expected outcome. Finally, some form of coverage measurement can be used to measure how many of the desired test scenarios have actually been tested, providing an indication of the quality of functional verification. The number of scenarios that should be considered in this process tracks the complexity of functional verification and thus has a doubly exponential growth rate.
Currently, functional verification can consume up to 70% of design effort and is typically a critical path in product development cycles. The bulk of this functional verification effort is spent on creating test cases to address the very large number of scenarios in a test plan.
Today, the majority of silicon re-spins of semiconductor products are due to logic bugs, with each spin adding significant delay and expense to project development. Logic bugs occur due to bug escapes in a verification process, and are caused by failure to test a bug scenario that led to the problem. Lack of quality in a verification process can be traced to four primary causes of bug escapes. First, comprehensive test plans are difficult to write, and a bug scenario might not have been considered in the test plan. Second, it can be difficult to create test cases that cover the large number of scenarios to be considered. A bug scenario might have been considered in a test plan, but there might have been insufficient time and resources to create a test case for the bug scenario. Third, there are difficulties in measuring coverage of scenarios that have been tested, and a failure to hit the bug scenario may not have been detected. Finally, inefficient use of compute resources may mean that a verification process never reached the test case for the bug scenario.
Creating a test plan that considers all scenarios to be tested is a difficult process. Test plans are typically paper documents containing laundry lists of items to be tested. Gaps can occur in ensuring that this list is complete. Further, with this approach it is difficult to explicitly define the possible interactions and dependencies between the various items to be tested. Strategies have been proposed advocating creating test plan documents in a structured hierarchical outline, while other strategies include annotating test plan documents with additional information, such as coverage targets, to be used later in a verification process. Neither of these strategies solve the problem of creating a comprehensive test plan.
Traditional approaches for constructing test cases can be divided into constrained random generation approaches and Backus-Naur Form (BNF) grammar-based approaches. Constrained random generation approaches are used to create test cases as a series of constrained random transactions. Using such approaches, one can generate all possible transactions for a given interface to a system. However, complex systems require a carefully orchestrated set of transactions on multiple interfaces to test most scenarios of interest. It can be difficult, time consuming, and compute intensive to construct such a set of transactions with a test generator using constrained random generation. Further, constrained random generation-based approaches provide no solution to predicting an expected result from a test case generated using such a technique. Finally, constrained random generation promotes a “spray and pray” strategy based on an argument that running enough random cases will ensure that all cases of interest are hit. In reality, this is an inefficient approach because the bulk of compute cycles are spent on repeatedly testing common cases with only a small number of cycles being spent testing corner and error cases.
BNF grammars have also been used to define valid sequences of transactions for generation of test cases. But, because complex designs tend to support a large number of functions and function variations, a BNF grammar required to fully verify a complex design can get impractically large. Large and complex BNF grammars can be difficult to review for completeness. Further, BNF grammars can imply a large number of test cases, in which it is difficult to control which cases should be tested or measure which portions of the BNF grammar are covered.
Prior work in measuring functional coverage of a test plan uses a number of different techniques. Examples of functional coverage techniques include: code coverage, assertion coverage, and transaction coverage techniques. Code coverage techniques measure how much of a source code for a design has been exercised. Assertion coverage techniques depend on insertion of numerous assertions into the design to check for correct behavior. Assertion coverage measures how many of these checks have been exercised. Transaction coverage techniques focus on measuring a mix of transactions that have been applied to each interface of a design. None of these techniques provide a direct measure of how much of a test plan has been covered and thus do not provide a direct measure of the quality of functional verification. Instead, quality of functional verification must be inferred from information provided by these techniques, and it is often difficult to differentiate between coverage cases that have been poorly tested, and those that are not reachable.
Functional verification continues to be a critical bottleneck in developing digital systems. Test generation and coverage analysis are typically limited by lack of efficiency and lack of quality. To address these limitations, a practical strategy for constructing a comprehensive test plan that does not leave out important bug scenarios is desired. Further, an automated process for generating test cases from such a test plan to alleviate the effort that must be put into creating test cases is also desired. Such a test generation process should cover the entire test plan while making efficient use of available compute resources to enable testing of all scenarios of interest. Finally, a measure of how much of the test plan has been covered in functional verification is also desired.